<!DOCTYPE html>
<html lang="zh-CN">
<head hexo-theme='https://github.com/volantis-x/hexo-theme-volantis/tree/4.1.5'>
  <meta charset="utf-8">
  <!-- SEO相关 -->
  
    
  
  <!-- 渲染优化 -->
  <meta http-equiv='x-dns-prefetch-control' content='on' />
  <link rel='dns-prefetch' href='https://cdn.jsdelivr.net'>
  <link rel="preconnect" href="https://cdn.jsdelivr.net" crossorigin>
  <meta name="renderer" content="webkit">
  <meta name="force-rendering" content="webkit">
  <meta http-equiv="X-UA-Compatible" content="IE=Edge,chrome=1">
  <meta name="HandheldFriendly" content="True" >
  <meta name="apple-mobile-web-app-capable" content="yes">
  <meta name="viewport" content="width=device-width, initial-scale=1, maximum-scale=1">

  <!-- 页面元数据 -->
  
  <title>论文阅读-Oblivious Database相关 - Schenk - Blog</title>
  
    <meta name="keywords" content="sgx,db">
  

  
    <meta name="description" content="论文阅读-Oblivious Database相关">
  

  <!-- feed -->
  

  <!-- import meta -->
  

  <!-- link -->
  
    <link rel="shortcut icon" type='image/x-icon' href="https://cdn.jsdelivr.net/gh/Schenk75/Source/logos/steroids.svg">
  

  <!-- import link -->
  

  
    
<link rel="stylesheet" href="/css/first.css">

  

  
  <link rel="stylesheet" href="/css/style.css" media="print" onload="this.media='all';this.onload=null">
  <noscript><link rel="stylesheet" href="/css/style.css"></noscript>
  

  <script id="loadcss"></script>

</head>

<body>
  

<header id="l_header" class="l_header auto shadow blur floatable show" style='opacity: 0' >
  <div class='container'>
  <div id='wrapper'>
    <div class='nav-sub'>
      <p class="title"></p>
      <ul class='switcher nav-list-h m-phone' id="pjax-header-nav-list">
        <li><a id="s-comment" class="fas fa-comments fa-fw" target="_self" href='javascript:void(0)'></a></li>
        
          <li><a id="s-toc" class="s-toc fas fa-list fa-fw" target="_self" href='javascript:void(0)'></a></li>
        
      </ul>
    </div>
		<div class="nav-main">
      
        
        <a class="title flat-box" target="_self" href='/'>
          
            <img no-lazy class='logo' src='https://cdn.jsdelivr.net/gh/Schenk75/Source@latest/logos/taiga.svg'/>
          
          
          
        </a>
      

			<div class='menu navigation'>
				<ul class='nav-list-h m-pc'>
          
          
          
            
            
              <li>
                <a class="menuitem flat-box faa-parent animated-hover" href=/
                  
                  
                  
                    id="home"
                  >
                  <i class='fab fa-stack-overflow fa-fw'></i>主页
                </a>
                
              </li>
            
          
          
            
            
              <li>
                <a class="menuitem flat-box faa-parent animated-hover" href=/categories/
                  
                  
                  
                    id="categories"
                  >
                  <i class='fas fa-folder-open fa-fw'></i>分类
                </a>
                
              </li>
            
          
          
            
            
              <li>
                <a class="menuitem flat-box faa-parent animated-hover" href=/tags/
                  
                  
                  
                    id="tags"
                  >
                  <i class='fas fa-tags fa-fw'></i>标签
                </a>
                
              </li>
            
          
          
            
            
              <li>
                <a class="menuitem flat-box faa-parent animated-hover" href=/archives/
                  
                  
                  
                    id="archives"
                  >
                  <i class='fas fa-archive fa-fw'></i>归档
                </a>
                
              </li>
            
          
          
            
            
              <li>
                <a class="menuitem flat-box faa-parent animated-hover" href=/friends/
                  
                  
                  
                    id="friends"
                  >
                  <i class='fas fa-link fa-fw'></i>友链
                </a>
                
              </li>
            
          
          
            
            
              <li>
                <a class="menuitem flat-box faa-parent animated-hover" href=/about/
                  
                  
                  
                    id="about"
                  >
                  <i class='fas fa-info-circle fa-fw'></i>关于
                </a>
                
              </li>
            
          
          
				</ul>
			</div>

      <div class="m_search">
        <form name="searchform" class="form u-search-form">
          <i class="icon fas fa-search fa-fw"></i>
          <input type="text" class="input u-search-input" placeholder="Search..." />
        </form>
      </div>

			<ul class='switcher nav-list-h m-phone'>
				
					<li><a class="s-search fas fa-search fa-fw" target="_self" href='javascript:void(0)'></a></li>
				
				<li>
          <a class="s-menu fas fa-bars fa-fw" target="_self" href='javascript:void(0)'></a>
          <ul class="menu-phone list-v navigation white-box">
            
              
            
              <li>
                <a class="menuitem flat-box faa-parent animated-hover" href=/
                  
                  
                  
                    id="home"
                  >
                  <i class='fab fa-stack-overflow fa-fw'></i>主页
                </a>
                
              </li>
            
          
            
              
            
              <li>
                <a class="menuitem flat-box faa-parent animated-hover" href=/categories/
                  
                  
                  
                    id="categories"
                  >
                  <i class='fas fa-folder-open fa-fw'></i>分类
                </a>
                
              </li>
            
          
            
              
            
              <li>
                <a class="menuitem flat-box faa-parent animated-hover" href=/tags/
                  
                  
                  
                    id="tags"
                  >
                  <i class='fas fa-tags fa-fw'></i>标签
                </a>
                
              </li>
            
          
            
              
            
              <li>
                <a class="menuitem flat-box faa-parent animated-hover" href=/archives/
                  
                  
                  
                    id="archives"
                  >
                  <i class='fas fa-archive fa-fw'></i>归档
                </a>
                
              </li>
            
          
            
              
            
              <li>
                <a class="menuitem flat-box faa-parent animated-hover" href=/friends/
                  
                  
                  
                    id="friends"
                  >
                  <i class='fas fa-link fa-fw'></i>友链
                </a>
                
              </li>
            
          
            
              
            
              <li>
                <a class="menuitem flat-box faa-parent animated-hover" href=/about/
                  
                  
                  
                    id="about"
                  >
                  <i class='fas fa-info-circle fa-fw'></i>关于
                </a>
                
              </li>
            
          
            
          </ul>
        </li>
			</ul>
		</div>
	</div>
  </div>
</header>

  <div id="l_body">
    <div id="l_cover">
  
    
        <div id="full" class='cover-wrapper post dock' style="display: none;">
          
            <div class='cover-bg lazyload placeholder' data-bg="https://cdn.jsdelivr.net/gh/Schenk75/Source@master/common/interstellar.jpg"></div>
          
          <div class='cover-body'>
  <div class='top'>
    
    
      <p class="title">Schenk - Blog</p>
    
    
      <p class="subtitle">SJTUer | Cuber</p>
    
  </div>
  <div class='bottom'>
    <div class='menu navigation'>
      <div class='list-h'>
        
          
            <a href="/categories/"
              
              
              id="categories">
              <i class='fas fa-folder-open fa-fw'></i><p>分类</p>
            </a>
          
            <a href="/tags/"
              
              
              id="tags">
              <i class='fas fa-tags fa-fw'></i><p>标签</p>
            </a>
          
            <a href="/archives/"
              
              
              id="archives">
              <i class='fas fa-archive fa-fw'></i><p>归档</p>
            </a>
          
            <a href="/friends/"
              
              
              id="friends">
              <i class='fas fa-link fa-fw'></i><p>友链</p>
            </a>
          
            <a href="/about/"
              
              
              id="about">
              <i class='fas fa-info-circle fa-fw'></i><p>关于</p>
            </a>
          
        
      </div>
    </div>
  </div>
</div>

          <div id="scroll-down" style="display: none;"><i class="fa fa-chevron-down scroll-down-effects"></i></div>
        </div>
    
  
  </div>

    <div id='safearea'>
      <div class='body-wrapper' id="pjax-container">
        

<div class='l_main'>
  <article class="article post white-box reveal md shadow floatable article-type-post" id="post" itemscope itemprop="blogPost">
  


  
  <div class="article-meta" id="top">
    
    
    
      <h1 class="title">
        论文阅读-Oblivious Database相关
      </h1>
      <div class='new-meta-box'>
        
          
            
<div class='new-meta-item author'>
  <a class='author' href="/" rel="nofollow">
    <img no-lazy src="https://cdn.jsdelivr.net/gh/Schenk75/Source@master/common/avatar.jpg">
    <p>Schenk</p>
  </a>
</div>

          
        
          
            
  <div class='new-meta-item category'>
    <a class='notlink'>
      <i class="fas fa-folder-open fa-fw" aria-hidden="true"></i>
      <a class="category-link" href="/categories/Paper-Reading/">Paper Reading</a><span class="sep"></span><a class="category-link" href="/categories/SGX/">SGX</a>
    </a>
  </div>


          
        
          
            <div class="new-meta-item date" itemprop="dateUpdated" datetime="2022-12-02T14:33:24+08:00">
  <a class='notlink'>
    <i class="fas fa-edit fa-fw" aria-hidden="true"></i>
    <p>更新于：2022年12月2日</p>
  </a>
</div>

          
        
          
            
  <div class="new-meta-item wordcount">
    <a class='notlink'>
      <i class="fas fa-keyboard fa-fw" aria-hidden="true"></i>
      <p>字数：6k字</p>
    </a>
  </div>
  <div class="new-meta-item readtime">
    <a class='notlink'>
      <i class="fas fa-hourglass-half fa-fw" aria-hidden="true"></i>
      <p>时长：23分钟</p>
    </a>
  </div>


          
        
          
            
  <div class="new-meta-item browse leancloud">
    <a class='notlink'>
      
      <div id="lc-pv" data-title="论文阅读-Oblivious Database相关" data-path="/2022/04/13/paper-reading/oblivious-db/">
        <i class="fas fa-eye fa-fw" aria-hidden="true"></i>
        <span id='number'><i class="fas fa-circle-notch fa-spin fa-fw" aria-hidden="true"></i></span>
        次浏览
      </div>
    </a>
  </div>


          
        
      </div>
    
  </div>


  
  <h2 id="不经意数据库相关研究">不经意数据库相关研究</h2>
<p>抵抗inference attack</p>
<p>关键是隐藏访问模式：隐藏访问内容+访问时间/访问次数/访问顺序等</p>
<h3 id="ObliDB-star2">ObliDB:star2:</h3>
<blockquote>
<ul>
<li>
<p>Proceedings of the VLDB Endowment，Volume 13，Issue 2，October 2019</p>
</li>
<li>
<p>Stanford University</p>
</li>
</ul>
</blockquote>
<h4 id="威胁模型：">威胁模型：</h4>
<ul>
<li>读取并篡改不可信内存</li>
<li>暂停和恢复Enclave执行</li>
<li>观察到对不可信内存的访问模式</li>
<li>监听网络通信</li>
<li>了解存储的数据的辅助信息</li>
<li>无法突破SGX远程认证</li>
<li><strong>假设</strong>：不经意内存有限</li>
</ul>
<h4 id="安全保证：">安全保证：</h4>
<ul>
<li>探测到任何篡改数据的恶意行为</li>
<li>只泄露查询选择率（select行的比例），表的大小（包括输出表和中间表）和查询方案</li>
<li>可选的padding模式，可以隐藏表的大小和查询选择率</li>
<li>在enclave外的数据经过加密和MAC计算，仅泄露大小</li>
<li>数据库中表的数量 &amp; 查询了哪张表不作隐藏</li>
</ul>
<h4 id="Overview：">Overview：</h4>
<img src="https://cdn.jsdelivr.net/gh/Schenk75/Source@master/notes/oblivious-db/image-20220404194724441.png" class="lazyload" data-srcset="https://cdn.jsdelivr.net/gh/Schenk75/Source@master/notes/oblivious-db/image-20220404194724441.png" srcset="" alt="image-20220404194724441" style="zoom:60%;" />
<ul>
<li>不经意数据库引擎支持小规模查询和分析查询（需要遍历整张表）</li>
<li>表加密存储在不可信内存但是访问模式被隐藏</li>
<li>两种存储方案：线性表、不经意索引（用于单点查询）</li>
<li>Enclave用于存储密钥、元数据，不经意算子在Enclave中执行</li>
</ul>
<h4 id="存储方案">存储方案</h4>
<p><strong>扁平化存储</strong></p>
<p>数据存储在相邻的块中，每次读/写都需要访问所有块（整张表），用于存储：</p>
<ul>
<li>小的表</li>
<li>操作后返回表的大部分区域的表</li>
<li>涉及读取全部或大部分表的分析</li>
</ul>
<p>数据的插入、更新、删除需遍历整张表，对未受影响的块进行虚拟写（重新写一遍所有数据并重新加密）</p>
<p><strong>索引存储</strong></p>
<p>对B+树的插入/删除操作会泄露树的结构信息 =&gt; 使用虚拟ORAM访问，填充所有插入/删除操作，使其访问次数与最坏情况匹配</p>
<p>优化：</p>
<ul>
<li>懒写回：只在必要的时候写入ORAM，否则将节点保留在enclave中</li>
<li>移除指向父节点的指针</li>
</ul>
<h3 id="Opaque">Opaque</h3>
<blockquote>
<ul>
<li>
<p>14th USENIX Symposium on Networked Systems Design and Implementation (NSDI 17)</p>
</li>
<li>
<p>UC Berkeley</p>
</li>
</ul>
</blockquote>
<blockquote>
<p>Opaque relies on oblivious sorts over the entire dataset. These systems are not efficient for more general workloads that may also include point queries.【ObliDB】(单点查询效率低)</p>
<p>仅达到了Level 1的不经意性，因为使用不经意内存池进行优化【O-Join】</p>
</blockquote>
<p>不经意分布式数据分析平台：</p>
<ul>
<li>引入一系列新的分布式关系运算符</li>
<li>新的查询规划技术，rule-based和cost-based</li>
<li>三种运行模式：加密模式、不经意模式、不经意填充模式</li>
</ul>
<h4 id="威胁模型">威胁模型</h4>
<ul>
<li>观察和修改网络通信</li>
<li>获取操作系统的root权限</li>
<li>观察enclave对不可信内存的访问模式</li>
<li>可以进行回滚攻击，将密封的数据恢复到之前的状态</li>
<li>不能破坏可信硬件</li>
<li>对Opaque源码的访问是不经意的</li>
</ul>
<h4 id="安全保证">安全保证</h4>
<p><strong>加密模式</strong></p>
<ul>
<li>数据加密和身份认证</li>
<li>self-verifying integrity</li>
</ul>
<p><strong>不经意模式</strong></p>
<ul>
<li>隐藏访问模式，但不隐藏访问的数据大小，以及Catalyst选择的查询方案</li>
</ul>
<p><strong>不经意填充模式</strong></p>
<ul>
<li>在不经意模式的基础上，进一步隐藏数据大小和查询方案</li>
</ul>
<h4 id="Overview">Overview</h4>
<img src="https://cdn.jsdelivr.net/gh/Schenk75/Source@master/notes/oblivious-db/image-20220405165557918.png" class="lazyload" data-srcset="https://cdn.jsdelivr.net/gh/Schenk75/Source@master/notes/oblivious-db/image-20220405165557918.png" srcset="" alt="image-20220405165557918" style="zoom:60%;" />
<h4 id="不经意执行">不经意执行</h4>
<ul>
<li>不经意排序（单机 &amp; 分布式）</li>
<li>不经意过滤（filter）</li>
<li>不经意聚合（group）</li>
<li>不经意连接（join）</li>
</ul>
<h4 id="查询规划">查询规划</h4>
<ul>
<li>成本模型：主要考虑不经意排序的次数</li>
<li>查询优化</li>
<li>混合敏感性：使用second path analysis来推断敏感表</li>
</ul>
<h3 id="OCQ">OCQ</h3>
<blockquote>
<ul>
<li>
<p>Proceedings of the Fifteenth European Conference on Computer Systems 2020</p>
</li>
<li>
<p>UC Berkeley</p>
</li>
</ul>
</blockquote>
<blockquote>
<p>OCQ[33]是一个不经意的协同竞争分析的通用框架，它建立在Opaque[87]的基础上，以分散的方式执行协同竞争查询。【Practical O-Join】</p>
</blockquote>
<p>多方不经意竞争分析的解决方案，而不是设计一个数据库</p>
<img src="https://cdn.jsdelivr.net/gh/Schenk75/Source@master/notes/oblivious-db/image-20220408145702098.png" class="lazyload" data-srcset="https://cdn.jsdelivr.net/gh/Schenk75/Source@master/notes/oblivious-db/image-20220408145702098.png" srcset="" alt="image-20220408145702098" style="zoom:60%;" />
<h4 id="主要贡献：">主要贡献：</h4>
<ul>
<li>不经意查询算法</li>
<li>schema-aware填充机制：防止两种数据泄露——enclave中的数据泄露和enclave外网络通信中的模式泄露</li>
<li>不经意规划器：决定在哪执行操作以及如何执行</li>
</ul>
<h4 id="不经意算法：">不经意算法：</h4>
<blockquote>
<p>Single-machine oblivious sorting can be done using sorting networks that perform a fixed sequence of compare-exchange operations. Asymptotically more compare-exchange operations are needed for oblivious sorting than for traditional sorting. An oblivious compare-exchange can be implemented via a comparison followed by a conditional swap of two equal-length buffers depending on the result of the comparison.</p>
<p>For data partitioned across multiple machines, oblivious sorting can be accomplished using a two-level sorting algorithm in which each partition is individually sorted using a sorting network, and records are sorted across partitions using an algorithm called column sort. Column sort consists of a fixed sequence of data exchange and intra-machine sorting<br>
that uses only 4 shuffles, compared to O(nlog2n) shuffles for a sorting-network-based distributed sort.</p>
</blockquote>
<img src="https://cdn.jsdelivr.net/gh/Schenk75/Source@master/notes/oblivious-db/image-20220408162528084.png" class="lazyload" data-srcset="https://cdn.jsdelivr.net/gh/Schenk75/Source@master/notes/oblivious-db/image-20220408162528084.png" srcset="" alt="image-20220408162528084" style="zoom:60%;" />
<h4 id="Overview-v2">Overview</h4>
<img src="https://cdn.jsdelivr.net/gh/Schenk75/Source@master/notes/oblivious-db/image-20220408163008436.png" class="lazyload" data-srcset="https://cdn.jsdelivr.net/gh/Schenk75/Source@master/notes/oblivious-db/image-20220408163008436.png" srcset="" alt="image-20220408163008436" style="zoom:60%;" />
<h3 id="Oblivious-join-star2">Oblivious join:star2:</h3>
<blockquote>
<ul>
<li>
<p>Proceedings of the VLDB Endowment 2020</p>
</li>
<li>
<p>University of Waterloo 滑铁卢大学</p>
</li>
</ul>
</blockquote>
<ul>
<li>
<p>提出时间复杂度为 $O(nlog^2n+mlogm)$ 的不经意equi-join算法，其中 $n$ 是输入表大小之和， $m$ 是输出表大小</p>
<ul>
<li>equi-join是指根据相等的条件来join两张表</li>
</ul>
</li>
<li>
<p>该算法只依赖于能够在加密数据上支持sorting network的计算模型</p>
</li>
<li>
<p>不隐藏输出大小和运行时间</p>
</li>
</ul>
<h4 id="在加密数据上进行计算">在加密数据上进行计算</h4>
<ul>
<li>Outsourced External Memory</li>
<li>Secure Cryptographic Coprocessors</li>
<li>TEE</li>
<li>Secure Multiparty Computation</li>
<li>Fully Homomorphic Encryption</li>
</ul>
<h4 id="不经意性划分">不经意性划分</h4>
<ul>
<li>Level 1：对公共内存的访问是不经意的，但需要非常数量的本地内存来执行non-oblivious计算</li>
<li>Level 2：对公共内存的访问是不经意的，且需要的本地内存大小是一个常数
<ul>
<li>访问程序的数据是不经意的，但是基于控制流访问的字节码没有隐藏。例如分支语句，条件本身是不经意的，但是跳转到的分支的字节码位置没有隐藏</li>
</ul>
</li>
<li>Level 3：程序的控制流，甚至处理器执行的指令，都与输入无关</li>
</ul>
<p>将Level 2的程序转变为Level 3的程序需另外满足3条限制：</p>
<ol>
<li>循环次数必须是常数（因为若根据变量来定循环次数，会很难隐藏执行循环的时间）</li>
<li>任何变量执行的最大分支数是一个常数</li>
<li>若一个程序暴露输出长度 $m$ ，则这一定在分配了 $m_0\in\Omega(m)$ 的内存之后</li>
</ol>
<h4 id="Overview-v3">Overview</h4>
<ul>
<li>输入两张未排序的表 $T_1$ 和 $T_2$ ，分别包含 $n_1$ 和 $n_2$ 对 $(j,d)$ ，其中 $j$ 表示参与join条件判断的属性， $d$ 是其他属性。输出记为 $T_1\bowtie T_2={(d_1,d_2)|(j,d_1)\in T_1, (j,d_2)\in T_2}$</li>
<li>使用固定大小的本地内存来实现Level 2的不经意性</li>
</ul>
<h4 id="算法">算法</h4>
<img src="https://cdn.jsdelivr.net/gh/Schenk75/Source@master/notes/oblivious-db/image-20220409170313852.png" class="lazyload" data-srcset="https://cdn.jsdelivr.net/gh/Schenk75/Source@master/notes/oblivious-db/image-20220409170313852.png" srcset="" alt="image-20220409170313852" style="zoom:40%;" />
<h3 id="ProDB">ProDB</h3>
<blockquote>
<ul>
<li>
<p>Information Systems 2021</p>
</li>
<li>
<p>The Hong Kong Polytechnic University 香港理工大学</p>
</li>
</ul>
</blockquote>
<ul>
<li>使用enclave+ORAM的方案来优化硬件资源不足的问题</li>
<li>提出SaP ORAM协议，用来实现enclave到不可信区的通信</li>
<li>不支持并发控制，回滚机制，数据库日志</li>
</ul>
<h4 id="Overview-v4">Overview</h4>
<ul>
<li>
<p>安全模型：Memory-secure DBMS</p>
<img src="https://cdn.jsdelivr.net/gh/Schenk75/Source@master/notes/oblivious-db/image-20220507125041216.png" class="lazyload" data-srcset="https://cdn.jsdelivr.net/gh/Schenk75/Source@master/notes/oblivious-db/image-20220507125041216.png" srcset="" alt="image-20220507125041216" style="zoom:67%;" />
</li>
<li>
<p>two-tier设计：</p>
<img src="https://cdn.jsdelivr.net/gh/Schenk75/Source@master/notes/oblivious-db/image-20220507125121199.png" class="lazyload" data-srcset="https://cdn.jsdelivr.net/gh/Schenk75/Source@master/notes/oblivious-db/image-20220507125121199.png" srcset="" alt="image-20220507125121199" style="zoom:67%;" />
<ul>
<li>core（部署在TEE中）
<ul>
<li>SQL Decryptor：在TEE中解密SQL query</li>
<li>Secure Query Processor (SQP)：与传统处理query的组件相同，除了I/O access</li>
<li>ORAM Analyzer (OA)：利用SQL query历史信息的meta-data来规划最优的分配数据块到ORAM树path的方案</li>
<li>ORAM Clients：每个client对应一个server，SQP通过client获取不可信内存中的数据</li>
</ul>
</li>
<li>shield（部署在不可信内存）
<ul>
<li>DBMS Main Process：主程序</li>
<li>ORAM Servers：树形结构，以ORAM-to-Disk机制将数据安全地写入磁盘</li>
</ul>
</li>
</ul>
</li>
<li>
<p>work-flow</p>
<img src="https://cdn.jsdelivr.net/gh/Schenk75/Source@master/notes/oblivious-db/image-20220507131334471.png" class="lazyload" data-srcset="https://cdn.jsdelivr.net/gh/Schenk75/Source@master/notes/oblivious-db/image-20220507131334471.png" srcset="" alt="image-20220507131334471" style="zoom:67%;" />
<img src="https://cdn.jsdelivr.net/gh/Schenk75/Source@master/notes/oblivious-db/image-20220507131443081.png" class="lazyload" data-srcset="https://cdn.jsdelivr.net/gh/Schenk75/Source@master/notes/oblivious-db/image-20220507131443081.png" srcset="" alt="image-20220507131443081" style="zoom:67%;" />
</li>
</ul>
<h4 id="SaP-ORAM">SaP ORAM</h4>
<p><strong>probabilistic lazy persistence</strong></p>
<img src="https://cdn.jsdelivr.net/gh/Schenk75/Source@master/notes/oblivious-db/image-20220507132908310.png" class="lazyload" data-srcset="https://cdn.jsdelivr.net/gh/Schenk75/Source@master/notes/oblivious-db/image-20220507132908310.png" srcset="" alt="image-20220507132908310" style="zoom:67%;" />
<ul>
<li>Tagged position map：tag-address-path映射</li>
<li>Update list：存储被SQL query更新的块（而不是被ORAM重加密更新的），不能被敌手知道哪些块在Update list中
<ul>
<li>probabilistic dirty-block-generation procedure</li>
</ul>
</li>
</ul>
<p><strong>SQL-aware path sharing</strong></p>
<p>目的：减少查询内和查询间的ORAM轮数</p>
<p>核心思想：在一轮ORAM中从树的path中获取多个块（ORAM Analyzer跟踪那些经常一起访问的块，并尽可能多地将它们放在同一ORAM树路径中）</p>
<p>具体方案：没细看</p>
<h3 id="Obladi">Obladi</h3>
<blockquote>
<ul>
<li>
<p>Proceedings of the 13th USENIX Symposium on Operating Systems Design and Implementation (OSDI’18)</p>
</li>
<li>
<p>Cornell University</p>
</li>
</ul>
</blockquote>
<blockquote>
<p>Obladi [28] considers concurrent ACID transactions but does not support indexes and only processes operations in batches over discrete time epochs.【ObliDB】</p>
<p>Obladi[32]是第一个在隐藏访问模式的同时提供ACID事务的系统。它批量处理操作，但不支持索引【Practical O-Join】</p>
</blockquote>
<p>【主要是事务和并发的实现】</p>
<p>第一个提供ACID事务的kv数据库</p>
<ul>
<li>容错机制</li>
<li>并发控制</li>
</ul>
<h3 id="Practical-Oblivious-Join">Practical Oblivious Join</h3>
<blockquote>
<ul>
<li>
<p>SIGMOD '22: Proceedings of the 2022 International Conference on Management of Data</p>
</li>
<li>
<p>西安电子科技大学，阿里巴巴</p>
</li>
</ul>
</blockquote>
<p>:star2:【参考文献整理】</p>
<ul>
<li>
<p>对以往的不经意Join算法进行整理比较</p>
</li>
<li>
<p>提出了两种用于一般二元equi-join的不经意算法</p>
<ul>
<li>oblivious sort-merge join</li>
<li>oblivious index nested-loop join</li>
</ul>
</li>
<li>
<p>通过扩展index nested-loop join来支持一些band join（如&quot;&lt;“和”&gt;&quot;）</p>
</li>
<li>
<p>使用index nested-loop join来支持多个表上的非循环equi-join</p>
</li>
</ul>
<h3 id="Oblivious-Query-Processing">Oblivious Query Processing</h3>
<blockquote>
<ul>
<li>Microsoft Research</li>
</ul>
</blockquote>
<h4 id="Contributions">Contributions</h4>
<ul>
<li>对安全查询处理的形式化定义</li>
<li>设计占用较小TM（Trusted Module）的不经意算法
<ul>
<li>定理1（Informal）：$O(log,n)$ TM空间占用的不经意算法的存在性</li>
<li>定理2（Informal）：I/O复杂度</li>
</ul>
</li>
<li>实现时间复杂度 $O(nlog,n)$ ，TM空间占用 $O(log,n)$ 的不经意算法
<ul>
<li>ORAM-based算法时间复杂度的下界为 $\Omega(nlog^2n)$</li>
</ul>
</li>
<li>除了不经意排序，所有算法都基于磁盘扫描；不经意排序基于磁盘搜索， 搜索次数 $O(log_{M/B}(n/B))\cdot o(n/B)$ 【M为TM内存，B为block大小】
<ul>
<li>ORAM-based算法磁盘搜索次数 $\Omega(\frac{n}{BlogM}log^2{\frac{n}{B}})$</li>
</ul>
</li>
</ul>
<h3 id="对比">对比</h3>
<table>
<thead>
<tr>
<th></th>
<th>数据库类型</th>
<th>支持</th>
<th>特点</th>
<th>实现</th>
</tr>
</thead>
<tbody>
<tr>
<td>ObliDB</td>
<td>关系型</td>
<td>索引</td>
<td></td>
<td>TEE+ORAM</td>
</tr>
<tr>
<td>Opaque</td>
<td>Spark SQL</td>
<td></td>
<td>分布式</td>
<td>TEE</td>
</tr>
<tr>
<td>OCQ</td>
<td>Opaque</td>
<td></td>
<td>分布式</td>
<td>TEE</td>
</tr>
<tr>
<td>ProDB</td>
<td>DBMS(关系型)</td>
<td></td>
<td>SaP ORAM协议</td>
<td>TEE+ORAM</td>
</tr>
<tr>
<td>Obladi</td>
<td>kv数据库</td>
<td>事务</td>
<td>并发ORAM</td>
<td>ORAM</td>
</tr>
<tr>
<td>CODBS</td>
<td>关系型(PostgresSQL)</td>
<td>索引</td>
<td>形式化证明:star2:</td>
<td>TEE+ORAM</td>
</tr>
<tr>
<td>O-Join</td>
<td>关系型</td>
<td></td>
<td>二元equi-join</td>
<td>TEE</td>
</tr>
<tr>
<td>Practical O-Join</td>
<td>关系型</td>
<td></td>
<td>综合Join</td>
<td>ORAM</td>
</tr>
<tr>
<td>O-Query</td>
<td>关系型</td>
<td></td>
<td>形式化证明:star2:</td>
<td>算法</td>
</tr>
</tbody>
</table>
<h2 id="不经意可搜索加密">不经意可搜索加密</h2>
<h3 id="CODBS">CODBS</h3>
<blockquote>
<ul>
<li>
<p>40th International Symposium on Reliable Distributed Systems (SRDS) 2021</p>
</li>
<li>
<p>University of Porto 葡萄牙波尔图大学</p>
</li>
</ul>
</blockquote>
<ul>
<li>提出一种新的<strong>不经意搜索方案</strong>CODBS来存储数据库索引，将搜索树拆分为L个较小的ORAM实例，而不是一个较大的ORAM</li>
<li>提出了Forest ORAM，这是一种用于存储数据库表的优化ORAM结构</li>
<li>提出了一种优化的不经意数据库体系结构，并在PostgreSQL之上实现了一个完整的解决方案</li>
<li>形式化证明</li>
</ul>
<h3 id="POSUP">POSUP</h3>
<blockquote>
<ul>
<li>
<p>Proceedings on Privacy Enhancing Technologies; Journal Volume: 2019</p>
</li>
<li>
<p>Oregon State University 俄勒冈州立大学</p>
</li>
</ul>
</blockquote>
<blockquote>
<p>POSUP [41] and Oblix [50] explore oblivious indexes over encrypted data using specialized ORAM constructions as building blocks, but do not support general queries.【ObliDB】</p>
</blockquote>
<p>使用Intel SGX开发不经意数据结构，在大数据集上提供实用的不经意搜索/更新操作</p>
<h3 id="Oblix">Oblix</h3>
<blockquote>
<ul>
<li>
<p>2018 IEEE Symposium on Security and Privacy (SP)</p>
</li>
<li>
<p>UC Berkeley</p>
</li>
</ul>
</blockquote>
<blockquote>
<p>POSUP [41] and Oblix [50] explore oblivious indexes over encrypted data using specialized ORAM constructions as building blocks, but do not support general queries.【ObliDB】</p>
</blockquote>
<p>不泄露访问模式，并且能够隐藏搜索结果的大小；支持更新（插入和删除），以及多个（可能是恶意的）用户</p>
<h3 id="Preserving-Access-Pattern-Privacy-in-SGX-Assisted-Encrypted-Search">Preserving Access Pattern Privacy in SGX-Assisted Encrypted Search</h3>
<blockquote>
<ul>
<li>
<p>27th International Conference on Computer Communication and Networks (ICCCN) 2018</p>
</li>
<li>
<p>The University of Auckland 奥克兰大学</p>
</li>
</ul>
</blockquote>
<ul>
<li>
<p>提出了一种SGX辅助的对加密数据进行搜索的方案</p>
</li>
<li>
<p>保护访问模式免受侧通道攻击，同时确保搜索效率（使用了B+树结构来保证搜索效率）</p>
</li>
<li>
<p>处理大型数据库，而不需要在SGX上长期存储（分批加载和处理树索引）</p>
</li>
<li>
<p>与基于oram的解决方案(如obildb)相比，我们的方案要快11倍以上</p>
</li>
</ul>
<h2 id="不经意性证明-分析">不经意性证明/分析</h2>
<h3 id="Memory-trace-oblivious-program-execution">Memory trace oblivious program execution</h3>
<h2 id="KV数据库TEE">KV数据库TEE</h2>
<h3 id="EdgelessDB">EdgelessDB</h3>
<p>开源项目，无相关论文，兼容MySQL</p>
<h3 id="Authenticated-key-value-stores-with-hardware-enclaves【相关性不大】">Authenticated key-value stores with hardware enclaves【相关性不大】</h3>
<blockquote>
<ul>
<li>Syracuse University 雪城大学</li>
</ul>
</blockquote>
<ul>
<li>支持查询认证的kv数据库，从而保护数据完整性</li>
<li>实现认证LSM树：eLSM（with small query proofs at selective<br>
tree levels），将内存数据存放在enclave外部
<ul>
<li>提出基于LSM树的新摘要结构：eLSM摘要，以append方式更新摘要</li>
</ul>
</li>
<li>基于Google LevelDB和Facebook RocksDB实现eLSM</li>
</ul>
<h4 id="LSM树">LSM树</h4>
<p>适用于<strong>写密集型</strong>workload</p>
<p>基本增删改查：<a target="_blank" rel="noopener" href="https://zhuanlan.zhihu.com/p/415799237">深入浅出分析LSM树（日志结构合并树） - 知乎 (zhihu.com)</a></p>
<p><a target="_blank" rel="noopener" href="https://zhuanlan.zhihu.com/p/181498475">LSM树详解 - 知乎 (zhihu.com)</a></p>
<p><img src="https://cdn.jsdelivr.net/gh/Schenk75/Source@master/notes/oblivious-db/UMjovFx.png" class="lazyload" data-srcset="https://cdn.jsdelivr.net/gh/Schenk75/Source@master/notes/oblivious-db/UMjovFx.png" srcset="" alt="LSM Tree architecture"></p>
<h4 id="安全定义">安全定义</h4>
<ul>
<li>Query integrity：读出的数据是否是之前合法的写请求写入的</li>
<li>Query completeness：读出的数据是否完整</li>
<li>Query freshness：读出的数据的时间戳是否最大</li>
</ul>
<h3 id="Aria">Aria</h3>
<blockquote>
<ul>
<li>
<p>2021 IEEE 37th International Conference on Data Engineering (ICDE)</p>
</li>
<li>
<p>清华</p>
</li>
</ul>
</blockquote>
<p>现实世界的工作负载通常表现出高度倾斜的访问模式：一小部分hot KV pair收到的请求比其他多得多</p>
<ul>
<li>引入基于软件的EPC空间管理器 <em>Secure Cache</em> ，为KV存储提供安全保障和高性能</li>
<li>深入研究了命中和未命中惩罚，从而优化了缓存策略</li>
<li>基于 <em>Secure Cache</em> 实现Aria，一个不依赖特定index structure的kv数据库</li>
</ul>
<h4 id="KV存储">KV存储</h4>
<ul>
<li>index structure：通过key找到一个KV pair
<ul>
<li>hash-based：简单而快速的点查询</li>
<li>tree-based：支持范围查询（有序存放key）</li>
</ul>
</li>
<li>storage manager：保存KV pair</li>
</ul>
<p>通常的设计是：将KV存储直接放在不受信任的内存中，并在EPC中构建安全元数据，以保护KV pair的完整性和机密性。这样的设计基于这样的事实：对不受信任内存中的KV pair或MAC的任何攻击都会导致从其相应计数器计算的MAC与存储在不受信任内存中的MAC之间的KV pair不匹配</p>
<img src="https://cdn.jsdelivr.net/gh/Schenk75/Source@master/notes/oblivious-db/image-20220513144149012.png" class="lazyload" data-srcset="https://cdn.jsdelivr.net/gh/Schenk75/Source@master/notes/oblivious-db/image-20220513144149012.png" srcset="" alt="image-20220513144149012" style="zoom:80%;" />
<img src="https://cdn.jsdelivr.net/gh/Schenk75/Source@master/notes/oblivious-db/image-20220513144327253.png" class="lazyload" data-srcset="https://cdn.jsdelivr.net/gh/Schenk75/Source@master/notes/oblivious-db/image-20220513144327253.png" srcset="" alt="image-20220513144327253" style="zoom:60%;" />
<h4 id="Secure-Cache"><em>Secure Cache</em></h4>
<img src="https://cdn.jsdelivr.net/gh/Schenk75/Source@master/notes/oblivious-db/image-20220513144458587.png" class="lazyload" data-srcset="https://cdn.jsdelivr.net/gh/Schenk75/Source@master/notes/oblivious-db/image-20220513144458587.png" srcset="" alt="image-20220513144458587" style="zoom:50%;" />
<ul>
<li><em>Secure Cache</em> 用于缓存最经常访问的MT节点，从而在访问这些节点时可以直接从 <em>Secure Cache</em> 里验证，消除了MT验证的开销（叶节点若是要验证，只需要沿着到根节点的路径，找到第一个在缓存中的节点即可）</li>
<li>语义优化：
<ul>
<li>消除metadata从enclave内部到外部的加密</li>
<li>避免clean缓存项的写回</li>
</ul>
</li>
<li>缓存命中优化：
<ul>
<li>将深层的节点固定在 <em>Secure Cache</em> 中（因为验证时用到的概率高）</li>
<li>采用FIFO策略来驱逐 <em>Secure Cache</em> 中的节点</li>
<li>若命中率小于一个阈值，停止swap</li>
</ul>
</li>
</ul>
<h4 id="实现">实现</h4>
<ul>
<li>连续Merkle树</li>
<li>用户空间堆分配器</li>
<li>解耦合设计</li>
<li>计数器管理</li>
<li>Put和Get实例
<ul>
<li>每次get需要解密多个kv pair才能得到想要的结果，是否有优化空间？</li>
</ul>
</li>
</ul>
<h3 id="SPEICHER">SPEICHER</h3>
<blockquote>
<ul>
<li>
<p>17th USENIX Conference on File and Storage Technologies (FAST 19) 2019</p>
</li>
<li>
<p>The University of Edinburgh 爱丁堡大学</p>
</li>
</ul>
</blockquote>
<blockquote>
<p>基于LSM树的三个设计更改：【Tweezer】</p>
<ul>
<li>必须调整MemTable以减少EPC的使用。Speicher重新设计了MemTable，使它的大部分(叶上的值)显式地存储在EPC外部，并具有加密保护</li>
<li>I/O调用必须由另一个线程在用户级别上处理，以避免在每次调用时都离开enclave上下文。Speicher使用基于Intel SPDK[1]的直接I/O库运行，这减少了额外上下文切换的成本</li>
<li>KVS应该有适当的时间戳，以击败回滚和分叉攻击。Speicher使用自己的异步单调计数器包装同步SGX单调计数器</li>
</ul>
</blockquote>
<ul>
<li>用于屏蔽执行的I/O库：I/O库在不退出enclave的情况下执行I/O操作
<ul>
<li>SPEICHER基于屏蔽执行框架SCONE实现</li>
</ul>
</li>
<li>异步可信单调计数器：确保数据新鲜度，利用KV存储中同步操作的延迟来异步更新计数器</li>
<li>安全LSM数据结构：部署在enclave外部，并保证<strong>完整性，机密性和新鲜性</strong></li>
<li>算法：设计和实现<strong>持久化</strong>KV数据库的操作：get, put, range queries, iterators, compaction, restore</li>
</ul>
<h4 id="威胁模型-v2">威胁模型</h4>
<ul>
<li>敌手可以控制整个系统软件堆栈，包括操作系统或虚拟机监控程序，并能够发起物理攻击，例如执行内存探测</li>
<li>防止回滚攻击和分叉攻击</li>
<li>无法抵御侧信道攻击</li>
</ul>
<h4 id="设计挑战">设计挑战</h4>
<ul>
<li>有限EPC大小：EPC分页切换开销大，因此需要将MemTable放在enclave外部，同时保证安全</li>
<li>不可信的存储介质：存储引擎持久化三种文件：SSTable，WAL，Manifest，需要保证这三种文件的安全（SGX本身不提供对有状态计算的安全保证），因此重新设计LSM数据结构</li>
<li>昂贵的I/O系统调用：SCONE提供异步系统调用接口，但不适合需要支持频繁I/O系统调用的存储系统，因此设计了一种新的I/O机制</li>
<li>可信计数器：用于保护存储在不可信存储介质中的数据的新鲜性，SGX可信计数器十分慢，因此设计了异步可信单调计数器</li>
</ul>
<h4 id="Overview-v5">Overview</h4>
<img src="https://cdn.jsdelivr.net/gh/Schenk75/Source@master/notes/oblivious-db/image-20220514193251916.png" class="lazyload" data-srcset="https://cdn.jsdelivr.net/gh/Schenk75/Source@master/notes/oblivious-db/image-20220514193251916.png" srcset="" alt="image-20220514193251916" style="zoom:67%;" />
<ul>
<li>
<p>SPEICHER controller：基于SCONE实现，提供可信执行环境、远程认证、enclave内部用户级多线程和内存管理的运行时支持</p>
</li>
<li>
<p>屏蔽I/O库：从enclave内部直接访问磁盘，而不需要昂贵的exit操作，通过SPDK实现</p>
</li>
<li>
<p>可信计数器：防止回滚攻击，设计异步单调计数器AMC</p>
</li>
<li>
<p>MemTable：key存放在enclave中的跳表里，value加密存放在不可信内存【存在线性增长导致EPC页切换的问题】<br>
<img src="https://cdn.jsdelivr.net/gh/Schenk75/Source@master/notes/oblivious-db/image-20220515135232118.png" class="lazyload" data-srcset="https://cdn.jsdelivr.net/gh/Schenk75/Source@master/notes/oblivious-db/image-20220515135232118.png" srcset="" alt="image-20220515135232118" style="zoom:50%;" /></p>
</li>
<li>
<p>SSTable：KV按序排列并经过加密，每个block的hash存放在footer，footer的hash记录在enclave中的Manifest中从而确保新鲜性<br>
<img src="https://cdn.jsdelivr.net/gh/Schenk75/Source@master/notes/oblivious-db/image-20220515140347727.png" class="lazyload" data-srcset="https://cdn.jsdelivr.net/gh/Schenk75/Source@master/notes/oblivious-db/image-20220515140347727.png" srcset="" alt="image-20220515140347727" style="zoom:50%;" /></p>
</li>
<li>
<p>Log文件：append-only</p>
<img src="https://cdn.jsdelivr.net/gh/Schenk75/Source@master/notes/oblivious-db/image-20220515142027419.png" class="lazyload" data-srcset="https://cdn.jsdelivr.net/gh/Schenk75/Source@master/notes/oblivious-db/image-20220515142027419.png" srcset="" alt="image-20220515142027419" style="zoom:50%;" />
- WAL：存放插入的KV pair直到top-level compaction，用于restore WAL
- Manifest：跟踪实时文件
</li>
</ul>
<h4 id="算法-v2">算法</h4>
<ul>
<li>Put：将KV pair添加到WAL，然后写到MemTable</li>
<li>Get：需要生成存在证明或不存在证明</li>
<li>Range queries：根据start key构建Iterator进行遍历，对于每个key，找到最顶层的value</li>
<li>Iterators</li>
<li>Restore：收集所有属于KV存储的文件（通过读取Manifest），然后重放所有变化到MemTable</li>
<li>Compaction</li>
</ul>
<h3 id="EnclaveCache">EnclaveCache</h3>
<blockquote>
<ul>
<li>
<p>Proceedings of the 20th International Middleware Conference 2019</p>
</li>
<li>
<p>SJTU</p>
</li>
</ul>
</blockquote>
<p>对多租户云环境的KV数据库进行用户隔离等保护【不相关】</p>
<h3 id="ShieldStore-star2">ShieldStore:star2:</h3>
<blockquote>
<ul>
<li>
<p>Proceedings of the Fourteenth EuroSys Conference 2019</p>
</li>
<li>
<p>School of Computing, KAIST 韩国科学技术院</p>
</li>
</ul>
</blockquote>
<blockquote>
<p>随着密钥空间的增长，ShieldStore由于bucket变长而承受着巨大的验证开销【Aria】</p>
</blockquote>
<img src="https://cdn.jsdelivr.net/gh/Schenk75/Source@master/notes/oblivious-db/image-20220515165456061.png" class="lazyload" data-srcset="https://cdn.jsdelivr.net/gh/Schenk75/Source@master/notes/oblivious-db/image-20220515165456061.png" srcset="" alt="image-20220515165456061" style="zoom:67%;" />
<h4 id="Baseline-kv存储">Baseline kv存储</h4>
<p>【不是直接用业界成熟的kv数据库，而是自己实现一个简单版本的内存kv存储】</p>
<ul>
<li>基于哈希的索引结构：高效点查询，范围查询困难</li>
<li>为相同的哈希值创建链表，来抗碰撞</li>
<li>server-side加密和计算数据</li>
</ul>
<h4 id="Overview-v6">Overview</h4>
<img src="https://cdn.jsdelivr.net/gh/Schenk75/Source@master/notes/oblivious-db/image-20220516132128859.png" class="lazyload" data-srcset="https://cdn.jsdelivr.net/gh/Schenk75/Source@master/notes/oblivious-db/image-20220516132128859.png" srcset="" alt="image-20220516132128859" style="zoom:67%;" />
<p>只将主要的密钥和meta-data存放在enclave中，主哈希表经过加密后存放在非可信区</p>
<h4 id="设计">设计</h4>
<p><strong>key-value加密</strong></p>
<img src="https://cdn.jsdelivr.net/gh/Schenk75/Source@master/notes/oblivious-db/image-20220516133315251.png" class="lazyload" data-srcset="https://cdn.jsdelivr.net/gh/Schenk75/Source@master/notes/oblivious-db/image-20220516133315251.png" srcset="" alt="image-20220516133315251" style="zoom:67%;" />
<ul>
<li>通过对hash索引使用keyed-hash函数，可以将hashed键分布中的信息泄漏降至最低【进一步优化？】</li>
<li>通过key hint来在一个bucket中快速找到对应的value</li>
<li>若一个key更新，IV/counter会增加；若创建新的kv pair，会插入到bucket的头部</li>
</ul>
<p><strong>完整性校验</strong></p>
<p>对每个bucket set维护一个Merkle root，而不是对所有kv pair维护一个Merkle tree【时间、空间复杂度分析？】</p>
<p><strong>持久化</strong></p>
<p>周期性snapshot</p>
<img src="https://cdn.jsdelivr.net/gh/Schenk75/Source@master/notes/oblivious-db/image-20220516142521396.png" class="lazyload" data-srcset="https://cdn.jsdelivr.net/gh/Schenk75/Source@master/notes/oblivious-db/image-20220516142521396.png" srcset="" alt="image-20220516142521396" style="zoom:50%;" />
<ul>
<li>parent进程密封enclave内的meta-data，child进程直接存储不可信内存中的哈希表</li>
<li>在snapshot的同时处理新的请求，使用临时表</li>
<li>使用SGX提供的单调计时器防止回滚攻击【使用效率更高的安全计时器?】</li>
</ul>
<h4 id="优化">优化</h4>
<ul>
<li>额外的堆分配器：在enclave内运行，分配外部不可信内存（为了减少OCALL）</li>
<li>MAC bucket：每个hash bucket维护一个，用来存放每个条目的MAC，从而快速计算merkle proof 而不用遍历整个chain<br>
<img src="https://cdn.jsdelivr.net/gh/Schenk75/Source@master/notes/oblivious-db/image-20220516144220072.png" class="lazyload" data-srcset="https://cdn.jsdelivr.net/gh/Schenk75/Source@master/notes/oblivious-db/image-20220516144220072.png" srcset="" alt="image-20220516144220072" style="zoom:50%;" /></li>
<li>多线程：不同的线程处理不同的hash key，从而避免同步，但线程数量只能固定，不能动态变化【使用Occlum改进？】<br>
<img src="https://cdn.jsdelivr.net/gh/Schenk75/Source@master/notes/oblivious-db/image-20220516144516641.png" class="lazyload" data-srcset="https://cdn.jsdelivr.net/gh/Schenk75/Source@master/notes/oblivious-db/image-20220516144516641.png" srcset="" alt="image-20220516144516641" style="zoom:50%;" /></li>
<li>搜索加密的key：使用1字节明文key的hash作为hint，从而减少需要解密的次数（只对匹配hint的key进行解密来判断是否是target key）</li>
</ul>
<h3 id="ZeroTrace-star2">ZeroTrace:star2:</h3>
<blockquote>
<ul>
<li>
<p>NDSS 2018</p>
</li>
<li>
<p>University of Waterloo 滑铁卢大学</p>
</li>
</ul>
</blockquote>
<blockquote>
<p>ZeroTrace[66]在set/dictionary/list接口上提供了一个新的不经意的get/put/insert操作库【Practical O-Join】</p>
</blockquote>
<ul>
<li>设计和实现了一个不经意内存管理器</li>
<li>设计和实现 ZeroTrace，一个用来不经意处理数据结构的库</li>
</ul>
<h4 id="安全威胁">安全威胁</h4>
<ul>
<li>enclave内对外部内存的访问是完全暴露于server的</li>
<li>enclave内部的执行不能保证不经意性</li>
<li>server可以随时终止enclave从而造成某些攻击</li>
<li>不抵抗硬件攻击、硬件制造的漏洞、拒绝服务攻击</li>
</ul>
<h4 id="定义">定义</h4>
<ul>
<li>enclave执行的不经意性（计算不可区分）</li>
<li>SGX的安全挑战
<ul>
<li>软件侧信道</li>
<li>不能对超出EPC范围的存储提供隐私/完整性保护</li>
<li>没有直接的IO/系统调用</li>
</ul>
</li>
<li>SGX的性能挑战
<ul>
<li>EPC大小限制</li>
<li>可信区和不可信区切换</li>
</ul>
</li>
<li>ORAM正确性和安全性定义（可忽略函数/计算不可区分）</li>
</ul>
<h4 id="ZeroTrace内存控制器">ZeroTrace内存控制器</h4>
<img src="https://cdn.jsdelivr.net/gh/Schenk75/Source@master/notes/oblivious-db/image-20220518095737812.png" class="lazyload" data-srcset="https://cdn.jsdelivr.net/gh/Schenk75/Source@master/notes/oblivious-db/image-20220518095737812.png" srcset="" alt="image-20220518095737812" style="zoom:67%;" />
<ul>
<li>
<p>client接口：<code>read(addr)</code> 和 <code>write(addr, data)</code></p>
</li>
<li>
<p>server处理： <code>FetchPath(leaf)</code> 和 <code>StorePath(tpath, leaf)</code></p>
</li>
<li>
<p>内存管理器enclave程序:</p>
<ul>
<li>
<p>初始化：将程序加载到enclave中</p>
</li>
<li>
<p>构筑块：</p>
<ul>
<li>不经意函数：根据汇编级别的函数库构建ORAM控制器</li>
<li>加密和哈希：使用AES-NI和SHA-256</li>
</ul>
</li>
<li>
<p>ORAM控制器：处理client请求 <code>(op, id, data*)</code></p>
<ul>
<li>不经意leaf-label检索</li>
<li>不经意block检索</li>
<li>不经意path重建</li>
</ul>
</li>
</ul>
</li>
<li>
<p>Fetch/Store path优化</p>
<ul>
<li>使用多个磁盘扩展带宽</li>
<li>缓存ORAM树的顶层</li>
</ul>
</li>
<li>
<p>安全性分析（informal）</p>
<img src="https://cdn.jsdelivr.net/gh/Schenk75/Source@master/notes/oblivious-db/image-20220518141008565.png" class="lazyload" data-srcset="https://cdn.jsdelivr.net/gh/Schenk75/Source@master/notes/oblivious-db/image-20220518141008565.png" srcset="" alt="image-20220518141008565" style="zoom:80%;" />
</li>
</ul>
<h4 id="持久化的完整性">持久化的完整性</h4>
<ul>
<li>定义fault tolerance的enclave协议</li>
<li>functionality和security</li>
<li>抵抗mix-and-match攻击</li>
<li>抵抗重放攻击</li>
</ul>
<h3 id="Precursor">Precursor</h3>
<blockquote>
<ul>
<li>
<p>Proceedings of the 22nd International Middleware Conference 2021</p>
</li>
<li>
<p>TU Braunschweig 布伦瑞克工业大学 德国</p>
</li>
</ul>
</blockquote>
<ul>
<li>
<p>利用TEE来提供保密性和完整性，同时依赖于RDMA进行低延迟和高带宽通信</p>
</li>
<li>
<p>将加密操作放在客户端，以防止服务器端CPU瓶颈</p>
</li>
<li>
<p>尽可能避免昂贵的TEE上下文切换，即安全区和非安全区的切换</p>
</li>
</ul>
<h3 id="TEE-KV">TEE-KV</h3>
<blockquote>
<ul>
<li>
<p>Proceedings of the ACM Symposium on Cloud Computing 2018</p>
</li>
<li>
<p>Tokyo University of Agriculture and Technology 东京农工大 &amp; 蚂蚁 &amp; Microsoft Research Asia 微软亚洲研究院</p>
</li>
</ul>
</blockquote>
<p>【只有一个Abstract，这是个啥？】</p>
<h3 id="Oblivious-key-value-stores-and-amplification-for-private-set-intersection">Oblivious key-value stores and amplification for private set intersection</h3>
<blockquote>
<ul>
<li>
<p>Annual International Cryptology Conference 2021</p>
</li>
<li>
<p>Oregon State University 俄勒冈州立大学</p>
</li>
</ul>
</blockquote>
<p>【形式化证明，没有用到SGX】</p>
<ul>
<li>
<p>引入了无关键值存储(OKVS)的抽象，确定并形式化了允许OKVS接入不同协议的重要属性</p>
</li>
<li>
<p>描述了放大技术，可以用来将较弱的OKVS引导为强OKVS</p>
</li>
</ul>
<h3 id="Tweezer">Tweezer</h3>
<blockquote>
<ul>
<li>20th USENIX Conference on File and Storage Technologies (fast22)</li>
<li>UNIST 韩国蔚山科学技术学院</li>
</ul>
</blockquote>
<ul>
<li>在Speicher基础上修改</li>
<li>根据Speicher论文自己实现了一个Speicher版本</li>
<li>TWEEZER比Speicher性能高出1.94 ~ 6.23×，使得由于机密计算导致的性能开销从16 ~ 30×减少到4 ~ 9×</li>
</ul>
<h4 id="不同于Speicher的三个关键设计">不同于Speicher的三个关键设计</h4>
<ol>
<li>无需构建横跨SSTable的Merkle树来确保LSM树的新鲜度，而是对不同的SSTable采用不同的key进行身份认证，使得攻击者无法在当前SSTable以外的任何地方找到其他数据块来执行重放攻击
<ul>
<li>Tweezer为每个SSTable创建并关联一个唯一的MAC key，基于LSM树的三个属性：每个SSTable的不可变性、每个Level的键的唯一性和每个数据块中的排序键</li>
</ul>
</li>
<li>每个数据块中键的顺序都是唯一且不变的，这使得Tweezer可以检测到任何对新鲜度的攻击，而无需为每个SSTable生成Merkle树
<ul>
<li>将MAC与每个键值对相关联，而不是与SSTable中的每个数据块相关联。Tweezer通过分别对每个键值对进行加密和身份验证，减少了EPC使用中的读放大。</li>
</ul>
</li>
<li>使用哈希链来对日志文件（WAL和Manifest）进行身份认证，而不使用计数器，Tweezer要求用户放置一个心跳事务来作为时间戳记录KVS版本，并在以后使用它来验证Tweezer的快照是否是最新的</li>
</ol>

  
  
    
    <div class='footer'>
      
      
      
      
    </div>
  
  
    


  <div class='article-meta' id="bottom">
    <div class='new-meta-box'>
      
        
          <div class="new-meta-item date">
  <a class='notlink'>
    <i class="fas fa-calendar-alt fa-fw" aria-hidden="true"></i>
    <p>发布于：2022年4月13日</p>
  </a>
</div>

        
      
        
          
  
  <div class="new-meta-item meta-tags"><a class="tag" href="/tags/sgx/" rel="nofollow"><i class="fas fa-hashtag fa-fw" aria-hidden="true"></i><p>sgx</p></a></div> <div class="new-meta-item meta-tags"><a class="tag" href="/tags/db/" rel="nofollow"><i class="fas fa-hashtag fa-fw" aria-hidden="true"></i><p>db</p></a></div>


        
      
    </div>
  </div>


  
  

  
    <div class="prev-next">
      
        <a class='prev' href='/2022/04/28/learning-notes/mit-6.824/'>
          <p class='title'><i class="fas fa-chevron-left" aria-hidden="true"></i>MIT 6.824 Distributed Systems 学习笔记</p>
          <p class='content'>Paper Reading
MapReduce
一个编程模型，用于大规模并行计算，以及采用re-execution进行容错处理

$Map$：输入键值对，输出一系列中间键值对，并将相同的中间键排...</p>
        </a>
      
      
        <a class='next' href='/2022/03/20/learning-notes/cryptography/'>
          <p class='title'>Introduction To Modern Cryptography笔记<i class="fas fa-chevron-right" aria-hidden="true"></i></p>
          <p class='content'>Chapter 1: Introduction
1.2 对称加密Setting

Kerckhoffs’ principle：要求加密算法的安全性只依赖于密钥的安全性，而加解密算法都应当可以公开...</p>
        </a>
      
    </div>
  
</article>


  

  






</div>
<aside class='l_side'>
  
  
    
    



  <section class="widget toc-wrapper shadow floatable desktop mobile" id="toc-div" >
    
  <header>
    
      <i class="fas fa-list fa-fw" aria-hidden="true"></i><span class='name'>本文目录</span>
    
  </header>


    <div class='content'>
        <ol class="toc"><li class="toc-item toc-level-2"><a class="toc-link" href="#%E4%B8%8D%E7%BB%8F%E6%84%8F%E6%95%B0%E6%8D%AE%E5%BA%93%E7%9B%B8%E5%85%B3%E7%A0%94%E7%A9%B6"><span class="toc-text">不经意数据库相关研究</span></a><ol class="toc-child"><li class="toc-item toc-level-3"><a class="toc-link" href="#ObliDB-star2"><span class="toc-text">ObliDB:star2:</span></a><ol class="toc-child"><li class="toc-item toc-level-4"><a class="toc-link" href="#%E5%A8%81%E8%83%81%E6%A8%A1%E5%9E%8B%EF%BC%9A"><span class="toc-text">威胁模型：</span></a></li><li class="toc-item toc-level-4"><a class="toc-link" href="#%E5%AE%89%E5%85%A8%E4%BF%9D%E8%AF%81%EF%BC%9A"><span class="toc-text">安全保证：</span></a></li><li class="toc-item toc-level-4"><a class="toc-link" href="#Overview%EF%BC%9A"><span class="toc-text">Overview：</span></a></li><li class="toc-item toc-level-4"><a class="toc-link" href="#%E5%AD%98%E5%82%A8%E6%96%B9%E6%A1%88"><span class="toc-text">存储方案</span></a></li></ol></li><li class="toc-item toc-level-3"><a class="toc-link" href="#Opaque"><span class="toc-text">Opaque</span></a><ol class="toc-child"><li class="toc-item toc-level-4"><a class="toc-link" href="#%E5%A8%81%E8%83%81%E6%A8%A1%E5%9E%8B"><span class="toc-text">威胁模型</span></a></li><li class="toc-item toc-level-4"><a class="toc-link" href="#%E5%AE%89%E5%85%A8%E4%BF%9D%E8%AF%81"><span class="toc-text">安全保证</span></a></li><li class="toc-item toc-level-4"><a class="toc-link" href="#Overview"><span class="toc-text">Overview</span></a></li><li class="toc-item toc-level-4"><a class="toc-link" href="#%E4%B8%8D%E7%BB%8F%E6%84%8F%E6%89%A7%E8%A1%8C"><span class="toc-text">不经意执行</span></a></li><li class="toc-item toc-level-4"><a class="toc-link" href="#%E6%9F%A5%E8%AF%A2%E8%A7%84%E5%88%92"><span class="toc-text">查询规划</span></a></li></ol></li><li class="toc-item toc-level-3"><a class="toc-link" href="#OCQ"><span class="toc-text">OCQ</span></a><ol class="toc-child"><li class="toc-item toc-level-4"><a class="toc-link" href="#%E4%B8%BB%E8%A6%81%E8%B4%A1%E7%8C%AE%EF%BC%9A"><span class="toc-text">主要贡献：</span></a></li><li class="toc-item toc-level-4"><a class="toc-link" href="#%E4%B8%8D%E7%BB%8F%E6%84%8F%E7%AE%97%E6%B3%95%EF%BC%9A"><span class="toc-text">不经意算法：</span></a></li><li class="toc-item toc-level-4"><a class="toc-link" href="#Overview-v2"><span class="toc-text">Overview</span></a></li></ol></li><li class="toc-item toc-level-3"><a class="toc-link" href="#Oblivious-join-star2"><span class="toc-text">Oblivious join:star2:</span></a><ol class="toc-child"><li class="toc-item toc-level-4"><a class="toc-link" href="#%E5%9C%A8%E5%8A%A0%E5%AF%86%E6%95%B0%E6%8D%AE%E4%B8%8A%E8%BF%9B%E8%A1%8C%E8%AE%A1%E7%AE%97"><span class="toc-text">在加密数据上进行计算</span></a></li><li class="toc-item toc-level-4"><a class="toc-link" href="#%E4%B8%8D%E7%BB%8F%E6%84%8F%E6%80%A7%E5%88%92%E5%88%86"><span class="toc-text">不经意性划分</span></a></li><li class="toc-item toc-level-4"><a class="toc-link" href="#Overview-v3"><span class="toc-text">Overview</span></a></li><li class="toc-item toc-level-4"><a class="toc-link" href="#%E7%AE%97%E6%B3%95"><span class="toc-text">算法</span></a></li></ol></li><li class="toc-item toc-level-3"><a class="toc-link" href="#ProDB"><span class="toc-text">ProDB</span></a><ol class="toc-child"><li class="toc-item toc-level-4"><a class="toc-link" href="#Overview-v4"><span class="toc-text">Overview</span></a></li><li class="toc-item toc-level-4"><a class="toc-link" href="#SaP-ORAM"><span class="toc-text">SaP ORAM</span></a></li></ol></li><li class="toc-item toc-level-3"><a class="toc-link" href="#Obladi"><span class="toc-text">Obladi</span></a></li><li class="toc-item toc-level-3"><a class="toc-link" href="#Practical-Oblivious-Join"><span class="toc-text">Practical Oblivious Join</span></a></li><li class="toc-item toc-level-3"><a class="toc-link" href="#Oblivious-Query-Processing"><span class="toc-text">Oblivious Query Processing</span></a><ol class="toc-child"><li class="toc-item toc-level-4"><a class="toc-link" href="#Contributions"><span class="toc-text">Contributions</span></a></li></ol></li><li class="toc-item toc-level-3"><a class="toc-link" href="#%E5%AF%B9%E6%AF%94"><span class="toc-text">对比</span></a></li></ol></li><li class="toc-item toc-level-2"><a class="toc-link" href="#%E4%B8%8D%E7%BB%8F%E6%84%8F%E5%8F%AF%E6%90%9C%E7%B4%A2%E5%8A%A0%E5%AF%86"><span class="toc-text">不经意可搜索加密</span></a><ol class="toc-child"><li class="toc-item toc-level-3"><a class="toc-link" href="#CODBS"><span class="toc-text">CODBS</span></a></li><li class="toc-item toc-level-3"><a class="toc-link" href="#POSUP"><span class="toc-text">POSUP</span></a></li><li class="toc-item toc-level-3"><a class="toc-link" href="#Oblix"><span class="toc-text">Oblix</span></a></li><li class="toc-item toc-level-3"><a class="toc-link" href="#Preserving-Access-Pattern-Privacy-in-SGX-Assisted-Encrypted-Search"><span class="toc-text">Preserving Access Pattern Privacy in SGX-Assisted Encrypted Search</span></a></li></ol></li><li class="toc-item toc-level-2"><a class="toc-link" href="#%E4%B8%8D%E7%BB%8F%E6%84%8F%E6%80%A7%E8%AF%81%E6%98%8E-%E5%88%86%E6%9E%90"><span class="toc-text">不经意性证明&#x2F;分析</span></a><ol class="toc-child"><li class="toc-item toc-level-3"><a class="toc-link" href="#Memory-trace-oblivious-program-execution"><span class="toc-text">Memory trace oblivious program execution</span></a></li></ol></li><li class="toc-item toc-level-2"><a class="toc-link" href="#KV%E6%95%B0%E6%8D%AE%E5%BA%93TEE"><span class="toc-text">KV数据库TEE</span></a><ol class="toc-child"><li class="toc-item toc-level-3"><a class="toc-link" href="#EdgelessDB"><span class="toc-text">EdgelessDB</span></a></li><li class="toc-item toc-level-3"><a class="toc-link" href="#Authenticated-key-value-stores-with-hardware-enclaves%E3%80%90%E7%9B%B8%E5%85%B3%E6%80%A7%E4%B8%8D%E5%A4%A7%E3%80%91"><span class="toc-text">Authenticated key-value stores with hardware enclaves【相关性不大】</span></a><ol class="toc-child"><li class="toc-item toc-level-4"><a class="toc-link" href="#LSM%E6%A0%91"><span class="toc-text">LSM树</span></a></li><li class="toc-item toc-level-4"><a class="toc-link" href="#%E5%AE%89%E5%85%A8%E5%AE%9A%E4%B9%89"><span class="toc-text">安全定义</span></a></li></ol></li><li class="toc-item toc-level-3"><a class="toc-link" href="#Aria"><span class="toc-text">Aria</span></a><ol class="toc-child"><li class="toc-item toc-level-4"><a class="toc-link" href="#KV%E5%AD%98%E5%82%A8"><span class="toc-text">KV存储</span></a></li><li class="toc-item toc-level-4"><a class="toc-link" href="#Secure-Cache"><span class="toc-text">Secure Cache</span></a></li><li class="toc-item toc-level-4"><a class="toc-link" href="#%E5%AE%9E%E7%8E%B0"><span class="toc-text">实现</span></a></li></ol></li><li class="toc-item toc-level-3"><a class="toc-link" href="#SPEICHER"><span class="toc-text">SPEICHER</span></a><ol class="toc-child"><li class="toc-item toc-level-4"><a class="toc-link" href="#%E5%A8%81%E8%83%81%E6%A8%A1%E5%9E%8B-v2"><span class="toc-text">威胁模型</span></a></li><li class="toc-item toc-level-4"><a class="toc-link" href="#%E8%AE%BE%E8%AE%A1%E6%8C%91%E6%88%98"><span class="toc-text">设计挑战</span></a></li><li class="toc-item toc-level-4"><a class="toc-link" href="#Overview-v5"><span class="toc-text">Overview</span></a></li><li class="toc-item toc-level-4"><a class="toc-link" href="#%E7%AE%97%E6%B3%95-v2"><span class="toc-text">算法</span></a></li></ol></li><li class="toc-item toc-level-3"><a class="toc-link" href="#EnclaveCache"><span class="toc-text">EnclaveCache</span></a></li><li class="toc-item toc-level-3"><a class="toc-link" href="#ShieldStore-star2"><span class="toc-text">ShieldStore:star2:</span></a><ol class="toc-child"><li class="toc-item toc-level-4"><a class="toc-link" href="#Baseline-kv%E5%AD%98%E5%82%A8"><span class="toc-text">Baseline kv存储</span></a></li><li class="toc-item toc-level-4"><a class="toc-link" href="#Overview-v6"><span class="toc-text">Overview</span></a></li><li class="toc-item toc-level-4"><a class="toc-link" href="#%E8%AE%BE%E8%AE%A1"><span class="toc-text">设计</span></a></li><li class="toc-item toc-level-4"><a class="toc-link" href="#%E4%BC%98%E5%8C%96"><span class="toc-text">优化</span></a></li></ol></li><li class="toc-item toc-level-3"><a class="toc-link" href="#ZeroTrace-star2"><span class="toc-text">ZeroTrace:star2:</span></a><ol class="toc-child"><li class="toc-item toc-level-4"><a class="toc-link" href="#%E5%AE%89%E5%85%A8%E5%A8%81%E8%83%81"><span class="toc-text">安全威胁</span></a></li><li class="toc-item toc-level-4"><a class="toc-link" href="#%E5%AE%9A%E4%B9%89"><span class="toc-text">定义</span></a></li><li class="toc-item toc-level-4"><a class="toc-link" href="#ZeroTrace%E5%86%85%E5%AD%98%E6%8E%A7%E5%88%B6%E5%99%A8"><span class="toc-text">ZeroTrace内存控制器</span></a></li><li class="toc-item toc-level-4"><a class="toc-link" href="#%E6%8C%81%E4%B9%85%E5%8C%96%E7%9A%84%E5%AE%8C%E6%95%B4%E6%80%A7"><span class="toc-text">持久化的完整性</span></a></li></ol></li><li class="toc-item toc-level-3"><a class="toc-link" href="#Precursor"><span class="toc-text">Precursor</span></a></li><li class="toc-item toc-level-3"><a class="toc-link" href="#TEE-KV"><span class="toc-text">TEE-KV</span></a></li><li class="toc-item toc-level-3"><a class="toc-link" href="#Oblivious-key-value-stores-and-amplification-for-private-set-intersection"><span class="toc-text">Oblivious key-value stores and amplification for private set intersection</span></a></li><li class="toc-item toc-level-3"><a class="toc-link" href="#Tweezer"><span class="toc-text">Tweezer</span></a><ol class="toc-child"><li class="toc-item toc-level-4"><a class="toc-link" href="#%E4%B8%8D%E5%90%8C%E4%BA%8ESpeicher%E7%9A%84%E4%B8%89%E4%B8%AA%E5%85%B3%E9%94%AE%E8%AE%BE%E8%AE%A1"><span class="toc-text">不同于Speicher的三个关键设计</span></a></li></ol></li></ol></li></ol>
    </div>
  </section>


  


</aside>



        
        
          <!--此文件用来存放一些不方便取值的变量-->
<!--思路大概是将值藏到重加载的区域内-->

<script>
  window.pdata={}
  pdata.ispage=true;
  pdata.postTitle="论文阅读-Oblivious Database相关";
  pdata.commentPath="";
  pdata.commentPlaceholder="";

  var l_header=document.getElementById("l_header");
  
  l_header.classList.add("show");
  
</script>

        
      </div>
      
  
  <footer class="footer clearfix">
    <br><br>
    
      
        <div class='copyright'>
        <p><a target="_blank" rel="noopener" href="https://github.com/Schenk75/Schenk75.github.io">Copyright © 2020-2022 Schenk</a></p>

        </div>
      
    
  </footer>


      <a id="s-top" class="fas fa-arrow-up fa-fw" href='javascript:void(0)'></a>
    </div>
  </div>
  <div>
    <script>
window.volantis={};
window.volantis.loadcss=document.getElementById("loadcss");
/********************脚本懒加载函数********************************/
function loadScript(src, cb) {
var HEAD = document.getElementsByTagName('head')[0] || document.documentElement;
var script = document.createElement('script');
script.setAttribute('type','text/javascript');
if (cb) script.onload = cb;
script.setAttribute('src', src);
HEAD.appendChild(script);
}
//https://github.com/filamentgroup/loadCSS
var loadCSS = function( href, before, media, attributes ){
	var doc = window.document;
	var ss = doc.createElement( "link" );
	var ref;
	if( before ){
		ref = before;
	}
	else {
		var refs = ( doc.body || doc.getElementsByTagName( "head" )[ 0 ] ).childNodes;
		ref = refs[ refs.length - 1];
	}
	var sheets = doc.styleSheets;
	if( attributes ){
		for( var attributeName in attributes ){
			if( attributes.hasOwnProperty( attributeName ) ){
				ss.setAttribute( attributeName, attributes[attributeName] );
			}
		}
	}
	ss.rel = "stylesheet";
	ss.href = href;
	ss.media = "only x";
	function ready( cb ){
		if( doc.body ){
			return cb();
		}
		setTimeout(function(){
			ready( cb );
		});
	}
	ready( function(){
		ref.parentNode.insertBefore( ss, ( before ? ref : ref.nextSibling ) );
	});
	var onloadcssdefined = function( cb ){
		var resolvedHref = ss.href;
		var i = sheets.length;
		while( i-- ){
			if( sheets[ i ].href === resolvedHref ){
				return cb();
			}
		}
		setTimeout(function() {
			onloadcssdefined( cb );
		});
	};
	function loadCB(){
		if( ss.addEventListener ){
			ss.removeEventListener( "load", loadCB );
		}
		ss.media = media || "all";
	}
	if( ss.addEventListener ){
		ss.addEventListener( "load", loadCB);
	}
	ss.onloadcssdefined = onloadcssdefined;
	onloadcssdefined( loadCB );
	return ss;
};
</script>
<script>
  
  loadCSS("https://cdn.jsdelivr.net/npm/@fortawesome/fontawesome-free@5.14/css/all.min.css", window.volantis.loadcss);
  
  
  
  
</script>
<!-- required -->

<script src="https://cdn.jsdelivr.net/npm/jquery@3.5/dist/jquery.min.js"></script>

<script>
  function pjax_fancybox() {
    $(".md .gallery").find("img").each(function () { //渲染 fancybox
      var element = document.createElement("a"); // a 标签
      $(element).attr("class", "fancybox");
      $(element).attr("pjax-fancybox", "");  // 过滤 pjax
      $(element).attr("href", $(this).attr("src"));
      if ($(this).attr("data-original")) {
        $(element).attr("href", $(this).attr("data-original"));
      }
      $(element).attr("data-fancybox", "images");
      var caption = "";   // 描述信息
      if ($(this).attr('alt')) {  // 判断当前页面是否存在描述信息
        $(element).attr('data-caption', $(this).attr('alt'));
        caption = $(this).attr('alt');
      }
      var div = document.createElement("div");
      $(div).addClass("fancybox");
      $(this).wrap(div); // 最外层套 div ，其实主要作用还是 class 样式
      var span = document.createElement("span");
      $(span).addClass("image-caption");
      $(span).text(caption); // 加描述
      $(this).after(span);  // 再套一层描述
      $(this).wrap(element);  // 最后套 a 标签
    })
    $(".md .gallery").find("img").fancybox({
      selector: '[data-fancybox="images"]',
      hash: false,
      loop: false,
      closeClick: true,
      helpers: {
        overlay: {closeClick: true}
      },
      buttons: [
        "zoom",
        "close"
      ]
    });
  };
  function SCload_fancybox() {
    if ($(".md .gallery").find("img").length == 0) return;
    loadCSS("https://cdn.jsdelivr.net/npm/@fancyapps/fancybox@3.5.7/dist/jquery.fancybox.min.css", document.getElementById("loadcss"));
    setTimeout(function() {
      loadScript('https://cdn.jsdelivr.net/gh/fancyapps/fancybox@3.5.7/dist/jquery.fancybox.min.js', pjax_fancybox)
    }, 1);
  };
  $(function () {
    SCload_fancybox();
  });
</script>


<!-- internal -->







  <script defer src="https://cdn.jsdelivr.net/npm/vanilla-lazyload@17.1.0/dist/lazyload.min.js"></script>
<script>
  // https://www.npmjs.com/package/vanilla-lazyload
  // Set the options globally
  // to make LazyLoad self-initialize
  window.lazyLoadOptions = {
    elements_selector: ".lazyload",
    threshold: 0
  };
  // Listen to the initialization event
  // and get the instance of LazyLoad
  window.addEventListener(
    "LazyLoad::Initialized",
    function (event) {
      window.lazyLoadInstance = event.detail.instance;
    },
    false
  );
  document.addEventListener('DOMContentLoaded', function () {
    lazyLoadInstance.update();
  });
  document.addEventListener('pjax:complete', function () {
    lazyLoadInstance.update();
  });
</script>




  
  
    <script>
      window.FPConfig = {
        delay: 0,
        ignoreKeywords: [],
        maxRPS: 5,
        hoverDelay: 25
      };
    </script>
    <script defer src="https://cdn.jsdelivr.net/gh/gijo-varghese/flying-pages@2.1.2/flying-pages.min.js"></script>
  




  <script src="https://cdn.jsdelivr.net/npm/clipboard@2/dist/clipboard.min.js"></script>
<script>
    var clipboard = new ClipboardJS('.btn-copy', {
        target: function (trigger) {
            return trigger.nextElementSibling
        }
    });
    function wait(callback, seconds) {
        var timelag = null;
        timelag = window.setTimeout(callback, seconds)
    }
    function pjax_initCopyCode() {
		if($(".highlight .code pre").length+$(".article pre code").length==0)return;
        var copyHtml = '';
        copyHtml += '<button class="btn-copy" data-clipboard-snippet="">';
        copyHtml += '<i class="fas fa-copy"></i><span>COPY</span>';
        copyHtml += '</button>';
        $(".highlight .code pre").before(copyHtml);
        $(".article pre code").before(copyHtml);
        clipboard.off('success').on('success', function (e) {
            let $btn = $(e.trigger);
            $btn.addClass('copied');
            let $icon = $($btn.find('i'));
            $icon.removeClass('fa-copy');
            $icon.addClass('fa-check-circle');
            let $span = $($btn.find('span'));
            $span[0].innerText = 'COPIED';
            wait(function () {
                $icon.removeClass('fa-check-circle');
                $icon.addClass('fa-copy');
                $span[0].innerText = 'COPY'
            }, 2000)
        });
        clipboard.off('error').on('error', function (e) {
            e.clearSelection();
            let $btn = $(e.trigger);
            $btn.addClass('copy-failed');
            let $icon = $($btn.find('i'));
            $icon.removeClass('fa-copy');
            $icon.addClass('fa-times-circle');
            let $span = $($btn.find('span'));
            $span[0].innerText = 'COPY FAILED';
            wait(function () {
                $icon.removeClass('fa-times-circle');
                $icon.addClass('fa-copy');
                $span[0].innerText = 'COPY'
            }, 2000)
        })
    }
    $(function () {
        pjax_initCopyCode()
    });
</script>










  <script defer src="https://cdn.jsdelivr.net/gh/Schenk75/Source@master/tools/busuanzi.pure.mini.js" data-pjax></script>


  
<script src="https://cdn.jsdelivr.net/npm/hexo-theme-volantis@4.1.5/source/js/app.min.js"></script>




  
  
<script src="https://cdn.jsdelivr.net/npm/hexo-theme-volantis@4.1.5/source/js/search.min.js"></script>

  


<!-- optional -->

  <script>
const SearchServiceimagePath="https://cdn.jsdelivr.net/gh/volantis-x/cdn-volantis@master/img/";
const ROOT =  ("/" || "/").endsWith('/') ? ("/" || "/") : ("//" || "/" );
function listenSearch(){
  
    customSearch = new HexoSearch({
      imagePath: SearchServiceimagePath
    });
  
}
document.addEventListener("DOMContentLoaded", listenSearch);

</script>











  <script defer>

  const LCCounter = {
    app_id: 'u9j57bwJod4EDmXWdxrwuqQT-MdYXbMMI',
    app_key: 'jfHtEKVE24j0IVCGHbvuFClp',
    custom_api_server: '',

    // 查询存储的记录
    getRecord(Counter, url, title) {
      return new Promise(function (resolve, reject) {
        Counter('get', '/classes/Counter?where=' + encodeURIComponent(JSON.stringify({url})))
          .then(resp => resp.json())
          .then(({results, code, error}) => {
            if (code === 401) {
              throw error;
            }
            if (results && results.length > 0) {
              var record = results[0];
              resolve(record);
            } else {
              Counter('post', '/classes/Counter', {url, title: title, times: 0})
                .then(resp => resp.json())
                .then((record, error) => {
                  if (error) {
                    throw error;
                  }
                  resolve(record);
                }).catch(error => {
                console.error('Failed to create', error);
                reject(error);
              });
            }
          }).catch((error) => {
          console.error('LeanCloud Counter Error:', error);
          reject(error);
        });
      })
    },

    // 发起自增请求
    increment(Counter, incrArr) {
      return new Promise(function (resolve, reject) {
        Counter('post', '/batch', {
          "requests": incrArr
        }).then((res) => {
          res = res.json();
          if (res.error) {
            throw res.error;
          }
          resolve(res);
        }).catch((error) => {
          console.error('Failed to save visitor count', error);
          reject(error);
        });
      });
    },

    // 构建自增请求体
    buildIncrement(objectId) {
      return {
        "method": "PUT",
        "path": `/1.1/classes/Counter/${ objectId }`,
        "body": {
          "times": {
            '__op': 'Increment',
            'amount': 1
          }
        }
      }
    },

    // 校验是否为有效的 UV
    validUV() {
      var key = 'LeanCloudUVTimestamp';
      var flag = localStorage.getItem(key);
      if (flag) {
        // 距离标记小于 24 小时则不计为 UV
        if (new Date().getTime() - parseInt(flag) <= 86400000) {
          return false;
        }
      }
      localStorage.setItem(key, new Date().getTime().toString());
      return true;
    },

    addCount(Counter) {
      var enableIncr = '' === 'true' && window.location.hostname !== 'localhost';
      enableIncr = true;
      var getterArr = [];
      var incrArr = [];
      // 请求 PV 并自增
      var pvCtn = document.querySelector('#lc-sv');
      if (pvCtn || enableIncr) {
        var pvGetter = this.getRecord(Counter, 'http://example.com' + '/#lc-sv', 'Visits').then((record) => {
          incrArr.push(this.buildIncrement(record.objectId))
          var eles = document.querySelectorAll('#lc-sv #number');
          if (eles.length > 0) {
            eles.forEach((el,index,array)=>{
              el.innerText = record.times + 1;
              if (pvCtn) {
                pvCtn.style.display = 'inline';
              }
            })
          }
        });
        getterArr.push(pvGetter);
      }

      // 请求 UV 并自增
      var uvCtn = document.querySelector('#lc-uv');
      if (uvCtn || enableIncr) {
        var uvGetter = this.getRecord(Counter, 'http://example.com' + '/#lc-uv', 'Visitors').then((record) => {
          var vuv = this.validUV();
          vuv && incrArr.push(this.buildIncrement(record.objectId))
          var eles = document.querySelectorAll('#lc-uv #number');
          if (eles.length > 0) {
            eles.forEach((el,index,array)=>{
              el.innerText = record.times + (vuv ? 1 : 0);
              if (uvCtn) {
                uvCtn.style.display = 'inline';
              }
            })
          }
        });
        getterArr.push(uvGetter);
      }

      // 请求文章的浏览数，如果是当前页面就自增
      var allPV = document.querySelectorAll('#lc-pv');
      if (allPV.length > 0 || enableIncr) {
        for (i = 0; i < allPV.length; i++) {
          let pv = allPV[i];
          let title = pv.getAttribute('data-title');
          var url = 'http://example.com' + pv.getAttribute('data-path');
          if (url) {
            var viewGetter = this.getRecord(Counter, url, title).then((record) => {
              // 是当前页面就自增
              let curPath = window.location.pathname;
              if (curPath.includes('index.html')) {
                curPath = curPath.substring(0, curPath.lastIndexOf('index.html'));
              }
              if (pv.getAttribute('data-path') == curPath) {
                incrArr.push(this.buildIncrement(record.objectId));
              }
              if (pv) {
                var ele = pv.querySelector('#lc-pv #number');
                if (ele) {
                  if (pv.getAttribute('data-path') == curPath) {
                    ele.innerText = (record.times || 0) + 1;
                  } else {
                    ele.innerText = record.times || 0;
                  }
                  pv.style.display = 'inline';
                }
              }
            });
            getterArr.push(viewGetter);
          }
        }
      }

      // 如果启动计数自增，批量发起自增请求
      if (enableIncr) {
        Promise.all(getterArr).then(() => {
          incrArr.length > 0 && this.increment(Counter, incrArr);
        })
      }

    },


    fetchData(api_server) {
      var Counter = (method, url, data) => {
        return fetch(`${ api_server }/1.1${ url }`, {
          method,
          headers: {
            'X-LC-Id': this.app_id,
            'X-LC-Key': this.app_key,
            'Content-Type': 'application/json',
          },
          body: JSON.stringify(data)
        });
      };
      this.addCount(Counter);
    },

    refreshCounter() {
      var api_server = this.app_id.slice(-9) !== '-MdYXbMMI' ? this.custom_api_server : `https://${ this.app_id.slice(0, 8).toLowerCase() }.api.lncldglobal.com`;
      if (api_server) {
        this.fetchData(api_server);
      } else {
        fetch('https://app-router.leancloud.cn/2/route?appId=' + this.app_id)
          .then(resp => resp.json())
          .then(({api_server}) => {
            this.fetchData('https://' + api_server);
          });
      }
    }

  };

  LCCounter.refreshCounter();

  document.addEventListener('pjax:complete', function () {
    LCCounter.refreshCounter();
  });
</script>








<script>
function listennSidebarTOC() {
  const navItems = document.querySelectorAll(".toc li");
  if (!navItems.length) return;
  const sections = [...navItems].map((element) => {
    const link = element.querySelector(".toc-link");
    const target = document.getElementById(
      decodeURI(link.getAttribute("href")).replace("#", "")
    );
    link.addEventListener("click", (event) => {
      event.preventDefault();
      window.scrollTo({
		top: target.offsetTop + 100,
		
		behavior: "smooth"
		
	  });
    });
    return target;
  });

  function activateNavByIndex(target) {
    if (target.classList.contains("active-current")) return;

    document.querySelectorAll(".toc .active").forEach((element) => {
      element.classList.remove("active", "active-current");
    });
    target.classList.add("active", "active-current");
    let parent = target.parentNode;
    while (!parent.matches(".toc")) {
      if (parent.matches("li")) parent.classList.add("active");
      parent = parent.parentNode;
    }
  }

  function findIndex(entries) {
    let index = 0;
    let entry = entries[index];
    if (entry.boundingClientRect.top > 0) {
      index = sections.indexOf(entry.target);
      return index === 0 ? 0 : index - 1;
    }
    for (; index < entries.length; index++) {
      if (entries[index].boundingClientRect.top <= 0) {
        entry = entries[index];
      } else {
        return sections.indexOf(entry.target);
      }
    }
    return sections.indexOf(entry.target);
  }

  function createIntersectionObserver(marginTop) {
    marginTop = Math.floor(marginTop + 10000);
    let intersectionObserver = new IntersectionObserver(
      (entries, observe) => {
        let scrollHeight = document.documentElement.scrollHeight + 100;
        if (scrollHeight > marginTop) {
          observe.disconnect();
          createIntersectionObserver(scrollHeight);
          return;
        }
        let index = findIndex(entries);
        activateNavByIndex(navItems[index]);
      },
      {
        rootMargin: marginTop + "px 0px -100% 0px",
        threshold: 0,
      }
    );
    sections.forEach((element) => {
      element && intersectionObserver.observe(element);
    });
  }
  createIntersectionObserver(document.documentElement.scrollHeight);
}

document.addEventListener("DOMContentLoaded", listennSidebarTOC);
document.addEventListener("pjax:success", listennSidebarTOC);
</script>

<!-- more -->




    
      


<script src="https://cdn.jsdelivr.net/npm/pjax@0.2.8/pjax.min.js"></script>


<script>
    var pjax;
    document.addEventListener('DOMContentLoaded', function () {
      pjax = new Pjax({
        elements: 'a[href]:not([href^="#"]):not([href="javascript:void(0)"]):not([pjax-fancybox])',
        selectors: [
          "title",
          "#l_cover",
          "#pjax-container",
          "#pjax-header-nav-list"
        ],
        cacheBust: false,   // url 地址追加时间戳，用以避免浏览器缓存
        timeout: 5000
      });
    });

    document.addEventListener('pjax:send', function (e) {
      //window.stop(); // 相当于点击了浏览器的停止按钮

      try {
        var currentUrl = window.location.pathname;
        var targetUrl = e.triggerElement.href;
        var banUrl = [""];
        if (banUrl[0] != "") {
          banUrl.forEach(item => {
            if(currentUrl.indexOf(item) != -1 || targetUrl.indexOf(item) != -1) {
              window.location.href = targetUrl;
            }
          });
        }
      } catch (error) {}

      window.subData = null; // 移除标题（用于一二级导航栏切换处）
      if (typeof $.fancybox != "undefined") {
        $.fancybox.close();    // 关闭弹窗
      }
      volantis.$switcher.removeClass('active'); // 关闭移动端激活的搜索框
      volantis.$header.removeClass('z_search-open'); // 关闭移动端激活的搜索框
      volantis.$wrapper.removeClass('sub'); // 跳转页面时关闭二级导航

      // 解绑事件 避免重复监听
      volantis.$topBtn.unbind('click');
      $('.menu a').unbind('click');
      $(window).unbind('resize');
      $(window).unbind('scroll');
      $(document).unbind('scroll');
      $(document).unbind('click');
      $('body').unbind('click');
	  
    });

    document.addEventListener('pjax:complete', function () {
      // 关于百度统计对 SPA 页面的处理：
      // 方案一：百度统计>管理>单页应用设置中，打开开启按钮即可对SPA进行统计。 https://tongji.baidu.com/web/help/article?id=324
      // 方案二：取消注释下列代码。 https://tongji.baidu.com/web/help/article?id=235
      // 

      // 关于谷歌统计对 SPA 页面的处理：
      // 当应用以动态方式加载内容并更新地址栏中的网址时，也应该更新通过 gtag.js 存储的网页网址。
      // https://developers.google.cn/analytics/devguides/collection/gtagjs/single-page-applications?hl=zh-cn
      

      $('.nav-main').find('.list-v').not('.menu-phone').removeAttr("style",""); // 移除小尾巴的移除
      $('.menu-phone.list-v').removeAttr("style",""); // 移除小尾巴的移除
      $('script[data-pjax], .pjax-reload script').each(function () {
        $(this).parent().append($(this).remove());
      });
      try{
          if (typeof $.fancybox == "undefined") {
            SCload_fancybox();
          } else {
            pjax_fancybox();
          }
        
        
        
        
        
          pjax_initCopyCode();
        
        
        
        
        
      } catch (e) {
        console.log(e);
      }
	  
    });

    document.addEventListener('pjax:error', function (e) {
	  
      window.location.href = e.triggerElement.href;
    });
</script>

    
  </div>
</body>
</html>
